/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	int ret = pf.open(indexname, mode);
	if(ret != 0) { return ret; } // Error
	
	BTLeafNode *leaf = new BTLeafNode;
	RecordId rid;
	int key = -1;
	
	if (pf.endPid() == 0){ // Doesn't already exist
		rootPid = 0; // Changes if insert and overflows so splits
		treeHeight = 1;
		// Set 1st slot to be -1 since no sibling, 1st recordID = root pid, height, -1

		leaf->setNextNodePtr(-1); // No sibling
		rid.pid = 0; // Set page of root to this node
		rid.sid = 1; // Set height of root to 1
		leaf->insert(key, rid); // Insert this info with key = -1 so this stays in front
		leaf->write(0, pf); // Write info back to disk to 
	}else{ // Index already exists, save pid and height info
		leaf->read(0, pf); // Read into node from disk
		leaf->readEntry(0, key, rid); // Read into our info from pid 0
		rootPid = rid.pid; // Read the (key,pid) info from the record file
		treeHeight = rid.sid;
		//fprintf(stdout, "rootpid: %d\n treeHeight: %d\n", rootPid, treeHeight);
	}
	delete leaf;
	return ret;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	BTLeafNode *leaf = new BTLeafNode;
	RecordId rid;
	int key = -1;
	rid.pid = rootPid; // Get new root node
	rid.sid = treeHeight; // Get new tree height
	
	leaf->read(0, pf); // Read into node from disk
	leaf->insert(key, rid); // Overwrite current info with new info
	leaf->write(0, pf); // Write info back to disk to save
	delete leaf;
    return pf.close();
}

/*
 * Recursively insert the key to the parent leaf nodes only! (Stop when parent is not full, or new root!)
 */
RC BTreeIndex::insertToParent(const PageId& parent, int key, const PageId& pid, const int searchKey)
{
	BTNonLeafNode *newroot = new BTNonLeafNode;
	BTNonLeafNode *nonleaf = new BTNonLeafNode;
	BTNonLeafNode *nonleafsib = new BTNonLeafNode;
	
	nonleaf->read(parent, pf);
	
	if(nonleaf->insert(key, pid) == 0){ // Parent has space
		nonleaf->write(parent, pf); // Write parent back into disk
	}else{ // no space in parent
		
		if(parent == rootPid){ // Special case, deal with creating new root
			int midKey;
			if (nonleaf->insertAndSplit(key, pid, *nonleafsib, midKey) != 0){
				delete newroot;
				delete nonleaf;
				delete nonleafsib;
				return -1; // Error, could not insert
			}
				
			// Now new root!
			newroot->initializeRoot(parent, midKey, pf.endPid()); 
				
			// All set, write everything back, IN ORDER!!
			nonleaf->write(parent, pf);
			nonleafsib->write(pf.endPid(), pf);
			newroot->write(pf.endPid(), pf); // Will give the pid after the sibling!
				
			// Change the tree height and the rootpid
			rootPid = (pf.endPid()-1);
			treeHeight = treeHeight+1;
		}else{ // Not dealing with full root node, but full node
			int midKey;
			if(nonleaf->insertAndSplit(key, pid, *nonleafsib, midKey) != 0){
				delete newroot;
				delete nonleaf;
				delete nonleafsib;
				return -1; // Error, could not insert
			}
			nonleaf->write(parent, pf);
			nonleafsib->write(pf.endPid(), pf);
			
			// Find parent of our parent
			PageId lastpid = rootPid;
			PageId nextpid = rootPid;
			for(int i = 1; i < treeHeight; i++){ // By the end, nextpid should carry the leafnode pid containing our key.
				lastpid = nextpid;
				nonleaf->read(lastpid, pf);
				nonleaf->locateChildPtr(searchKey, nextpid);
				if(nextpid == parent){
					break;
				}
			}
			
			// ADD midKey, pf.endPid()-1 TO THE PARENT OF NONLEAF recursively
			return insertToParent(lastpid, midKey, pf.endPid()-1, searchKey); // get parent pid
		}
	}
	
	delete newroot;
	delete nonleaf;
	delete nonleafsib;
    return 0;
}


/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	BTLeafNode *leaf = new BTLeafNode;
	BTLeafNode *sib = new BTLeafNode;
	BTNonLeafNode *nonleaf = new BTNonLeafNode;
	BTNonLeafNode *nonleafsib = new BTNonLeafNode;
	
	// If only one (root) node
	if(treeHeight == 1){ // There is only one root (leaf) node
		leaf->read(rootPid, pf); // rootPid = 0
		if(leaf->insert(key, rid) != 0){ // We could not insert, need to split
			leaf->setNextNodePtr(pf.endPid()); // The sibling will be in the next available pid
			int sibKey;
			if (leaf->insertAndSplit(key, rid, *sib, sibKey) != 0){
				delete leaf;
				delete sib;
				delete nonleaf;
				delete nonleafsib;
				return -1; // Error, could not insert
			}
			
			// Now new root!
			nonleaf->initializeRoot(rootPid, sibKey, pf.endPid()); 
			
			// All set, write everything back, IN ORDER!!
			leaf->write(rootPid, pf);
			sib->write(pf.endPid(), pf);
			nonleaf->write(pf.endPid(), pf); // Will give the pid after the sibling!
			
			// Change the tree height and the rootpid
			rootPid = (pf.endPid()-1);
			treeHeight = treeHeight+1;
		}else{ // Inserted, need to write!
			leaf->write(rootPid, pf);
			//leaf->printBuffer();
		}
	}else{ // There is more than one node, traverse to find leaf node.
		PageId lastpid = rootPid;
		PageId nextpid = rootPid;
		for(int i = 1; i < treeHeight; i++){ // By the end, nextpid should carry the leafnode pid containing our key.
			lastpid = nextpid; // Now we also store the parent node pid
			nonleaf->read(nextpid, pf);
			if(nonleaf->locateChildPtr(key, nextpid) != 0){
				delete leaf;
				delete sib;
				delete nonleaf;
				delete nonleafsib;
				return -1; // Should not occur that we dont get child pointer
			}
		}
		nonleaf->read(lastpid, pf); // Get the parent node
		leaf->read(nextpid, pf); // Get our leaf node
		
		/* Now we need to insert into leaf node. 3 cases:
			1) leaf has space, insert
			2) leaf doesn't have space, parent does
			3) leaf and parent do not have space
		*/
		int sibKey;
		if(leaf->insert(key, rid) == 0){ // Success! Case 1: Leaf has space, insert
			leaf->write(nextpid, pf); // Write back the insert
		}else{ // leaf does not have space. Cases 2 and 3
			leaf->setNextNodePtr(pf.endPid()); // The sibling will be in the next available pid
			if (leaf->insertAndSplit(key, rid, *sib, sibKey) != 0){
				delete leaf;
				delete sib;
				delete nonleaf;
				delete nonleafsib;
				return -1; // Error, could not insert
			}
			leaf->write(nextpid, pf);
			sib->write(pf.endPid(), pf);
			
			if(insertToParent(lastpid, sibKey, pf.endPid()-1, key) != 0){
				delete leaf;
				delete sib;
				delete nonleaf;
				delete nonleafsib;
				return -1; // Error, could not insert
			}
			
			/*if(nonleaf->insert(sibKey, pf.endPid()-1) == 0){ // Case 2: Parent has space
				nonleaf->write(lastpid, pf); // Write parent back intodisk
			}else{ // Case 3: no space in child and parent
				int midKey;
				if(nonleaf->insertAndSplit(sibKey, pf.endPid()-1, *nonleafsib, midKey) != 0){
					delete leaf;
					delete sib;
					delete nonleaf;
					delete nonleafsib;
					return -1; // Error, could not insert
				}
				nonleaf->write(lastpid, pf);
				nonleafsib->write(pf.endPid(), pf);
				// STILL NEED TO ADD midKey, pf.endPid()-1 TO THE PARENT OF NONLEAF
			}*/
		}
	}
	
	delete leaf;
	delete sib;
	delete nonleaf;
	delete nonleafsib;
	
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	BTLeafNode *leaf = new BTLeafNode;
	BTNonLeafNode *nonleaf = new BTNonLeafNode;
	
	PageId lastpid = rootPid;
	PageId nextpid = rootPid;
	for(int i = 1; i < treeHeight; i++){ // By the end, nextpid should carry the leafnode pid containing our key.
		lastpid = nextpid; // Now we also store the parent node pid
		nonleaf->read(nextpid, pf);
		if(nonleaf->locateChildPtr(searchKey, nextpid) != 0){
			delete leaf;
			delete nonleaf;
			return -1; // Should not occur that we dont get child pointer
		}
	}
	nonleaf->read(lastpid, pf); // Get the parent node
	leaf->read(nextpid, pf); // Get our leaf node
	cursor.pid = nextpid;
	//fprintf(stdout, "rootpid: %d\n treeHeight: %d\n searchKey: %d\n", rootPid, treeHeight, searchKey);
	//leaf->printBuffer();
	
	//leaf->read(cursor.pid, pf); // Read into node from disk
	if(leaf->locate(searchKey, cursor.eid) != 0){ // error!!
		//cursor.pid = leaf->getNextNodePtr();
		/*if(cursor.pid == -1){ // This means there is no sibling node...
			delete leaf; 
			return -1; 
		} 
		cursor.eid = 0;
		return locate(searchKey, cursor); // Try locating in sibling*/
		delete leaf; 
		delete nonleaf;
		return -1;
	}
	
	delete leaf; 
	delete nonleaf;
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode *leaf = new BTLeafNode;
	
	if(leaf->read(cursor.pid, pf) != 0){ return -1; } // Read into node from disk, if error return
	if(leaf->readEntry(cursor.eid, key, rid) != 0){ // Get info, if error, move to next leaf node if possible
		cursor.pid = leaf->getNextNodePtr();
		if(cursor.pid == -1){ // This means there is no sibling node...
			delete leaf;
			return -1; 
		}
		cursor.eid = 0;
		return readForward(cursor, key, rid);
	} 
	
	cursor.eid = (cursor.eid + 1);
	
	delete leaf; 
    return 0;
}
